/*
给你一个字符串 s ，考虑其所有 重复子串 ：即，s 的连续子串，在 s 中出现 2 次或更多次。这些出现之间可能存在重叠。

返回 任意一个 可能具有最长长度的重复子串。如果 s 不含重复子串，那么答案为 "" 。

 

示例 1：

输入：s = "banana"
输出："ana"
示例 2：

输入：s = "abcd"
输出：""
 

提示：

2 <= s.length <= 3 * 104
s 由小写英文字母组成

来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/longest-duplicate-substring
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
*/

#include "../stdc++.h"

// 二分查找 + Rabin-Karp 字符串编码
typedef pair<long long, long long> pll;
class Solution {
public:
    string longestDupSubstring(string s) {
        srand(static_cast<unsigned>(time(nullptr)));
        // 生成两个进制
        int a1 = random() % 75 + 26;
        int a2 = random() % 75 + 26;

        // 生成两个模
        int mod1 = random() % (INT_MAX - 1000000006) + 1000000006;
        int mod2 = random() % (INT_MAX - 1000000006) + 1000000006;

        // 先对所有字符进行编码
        int n = s.size();
        vector<int> arr(n, 0);
        for (int i{0}; i < n; ++i) {
            arr[i] = s[i] - 'a';
        }

        // 二分查找的范围是[1, n-1]
        int left{1};
        int right{n - 1};
        int length{0};
        int start{-1};
        while (left <= right) {
            int m = left + (right - left + 1) / 2;
            int index = check(arr, m, a1, a2, mod1, mod2);
            if (index != -1) {
                // 有重复子串，移动左边界
                left = m + 1;
                length = m;
                start = index;
            } else {
                // 无重复子串，移动有边界
                right = m - 1;
            }
        }
        return (start != -1) ? s.substr(start, length) : "";
    }
private:
    int check(const vector<int>& arr, int m, int a1, int a2, int mod1, int mod2) {
        int n = arr.size();
        long long aL1 = pow(a1, m, mod1);
        long long aL2 = pow(a2, m, mod2);
        long long h1{0};
        long long h2{0};
        for (int i{0}; i < m; ++i) {
            h1 = (h1 * a1 % mod1 + arr[i]) % mod1;
            h2 = (h2 * a2 % mod2 + arr[i]) % mod2;
            if (h1 < 0) {
                h1 += mod1;
            }
            if (h2 < 0) {
                h2 += mod2;
            }
        }
        // 存储一个编码组合是否出现过
        set<pll> seen;
        seen.emplace(h1, h2);
        for (int start{1}; start <= n - m; ++start) {
            h1 = (h1 * a1 % mod1 - arr[start - 1] * aL1 % mod1 + arr[start + m - 1]) % mod1;
            h2 = (h2 * a2 % mod2 - arr[start - 1] * aL2 % mod2 + arr[start + m - 1]) % mod2;
            if (h1 < 0) {
                h1 += mod1;
            }
            if (h2 < 0) {
                h2 += mod2;
            }
            // 如果重复，则返回重复串的七点
            if (seen.count(make_pair(h1, h2)) != 0) {
                return start;
            }
            seen.emplace(h1, h2);
        }
        // 没有重复，则返回-1
        return -1;
    }
    long long pow(int a, int m, int mod) {
        long long res{1};
        long long contribute{a};
        while (m > 0) {
            if (m % 2 == 1) {
                res = res * contribute % mod;
                if (res < 0) {
                    res += mod;
                }
            }
            contribute = contribute * contribute % mod;
            if (contribute < 0) {
                contribute += mod;
            }
            m /= 2;
        }
        return res;
    }
};
